﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
这道题还是有很多解法
我采取优先级队列的解法
好像还有归并的解法
*/

//每日一题_06
//BM5 合并k个已排序的链表
//https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
class Solution {
public:
    struct compare
    {
        //重载比较方式
        bool operator()(ListNode* a, ListNode* b)
        {
            return  a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        //小顶堆
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;

        //遍历链表
        //只拿第一个链表头
        for (int i = 0; i < lists.size(); i++)
        {
            //不为空则进堆
            if (lists[i] != nullptr)
                pq.push(lists[i]);
        }

        //加一个表头
        ListNode* res = new ListNode(-1);
        ListNode* head = res;
        //直到小顶堆为空
        while (!pq.empty()) {
            //取出最小的元素
            ListNode* temp = pq.top();
            pq.pop();
            head->next = temp;
            head = head->next;
            //每次取出链表的后一个元素加入小顶堆
            if (temp->next != nullptr)
                pq.push(temp->next);
        }
        return res->next;
    }
};
